Các thuật toán di truyền (GAs)là các thủ tục tìm kiếm toàn cục ngẫu nhiên lấy cảm hứng từ các nguyên lý của tiến hóa tự nhiên, đặc biệt là 'sự sống sót của những cá thể thích nghi nhất' theo Darwin và sự tái tổ hợp gen.
1. Các khung biểu diễn
- Các thuật toán di truyền dạng chuẩn:Sử dụng biểu diễn chuỗi nhị phân hoặc mã Gray để mã hóa các biến quyết định.
- Các thuật toán di truyền dạng thực (RCGAs):Thao tác trực tiếp trên các vector số thực, thường hiệu quả hơn cho bài toán tối ưu liên tục.
2. Vòng lặp tiến hóa
Là một quá trình lặp lại gồm đánh giá, chọn lọc và sinh sản. Một khái niệm then chốt là sự khác biệt giữa kiểu gen (chuỗi bit đã được mã hóa/nhịp tử) và kiểu hình (giá trị biến quyết định đã được giải mã trong không gian bài toán thực tế).
Phép ánh xạ từ một chuỗi nhị phân sang giá trị thực $x \in [a, b]$ được xác định bởi:
$$x = a + \frac{giá_trị_thập_phân \times (b - a)}{2^L - 1}$$
Trong đó $L$ là độ dài bit của nhịp tử.
Vực thẳm Hamming
Hãy cẩn thận với vực thẳm Hammingtrong mã hóa nhị phân chuẩn—tình huống mà các số thập phân liền kề (ví dụ như 7 và 8) có mẫu bit nhị phân hoàn toàn khác nhau (
0111 so với 1000), khiến việc tìm kiếm cục bộ của thuật toán di truyền trở nên khó khăn.
Triển khai bằng Python: Giải mã nhị phân thành số thực
Câu hỏi 1
Tại sao mã Gray thường được ưa chuộng hơn mã nhị phân chuẩn trong các thuật toán di truyền?
Câu hỏi 2
Nếu xác suất đột biến (p) được đặt quá cao (ví dụ: p = 0.5), kết quả có khả năng xảy ra là gì?
Trường hợp nghiên cứu: Tối ưu hóa bộ phận cầu
Đọc tình huống dưới đây và trả lời các câu hỏi.
Bạn đang tối ưu hóa thiết kế một bộ phận cầu, trong đó biến quyết định là "Độ dày vật liệu".
- Độ dày phải nằm trong khoảng từ 0,0 mm đến 10,23 mm.
- Bạn đang sử dụng một thuật toán di truyền dạng chuẩn với 10-bitbiểu diễn chuỗi nhị phân.
Câu
1. Nếu một cá thể có nhịp tử
0000000000, thì độ dày đã giải mã là bao nhiêu?Đáp án: 0,0 mm
Chuỗi nhị phân
Chuỗi nhị phân
0000000000bằng 0 ở hệ thập phân. Sử dụng công thức $x = a + \frac{thập_phân \times (b-a)}{2^L - 1}$, ta được $0,0 + \frac{0 \times (10,23 - 0,0)}{1023} = 0,0$.
Câu
2. Tính độ chính xác tìm kiếm (thay đổi nhỏ nhất có thể của độ dày) đối với cấu hình 10-bit này.
Đáp án: 0,01 mm
Độ chính xác được định nghĩa là phạm vi chia cho giá trị thập phân lớn nhất có thể. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01$ mm.
Độ chính xác được định nghĩa là phạm vi chia cho giá trị thập phân lớn nhất có thể. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01$ mm.
Câu
3. Trong quá trình chọn lọc, cá thể A có độ thích nghi là 10 và cá thể B có độ thích nghi là 30. Sử dụng phương pháp chọn lọc bánh xe Roulette, xác suất để chọn B thay vì A là bao nhiêu?
Đáp án: 75%
Tổng độ thích nghi = $10 + 30 = 40$. Xác suất chọn B = $\frac{30}{40} = 0,75$ hay 75%. (Tỷ lệ 3:1).
Tổng độ thích nghi = $10 + 30 = 40$. Xác suất chọn B = $\frac{30}{40} = 0,75$ hay 75%. (Tỷ lệ 3:1).